A wireless multi-hop network consists of mobile or static nodes. These nodes function as routers or hosts or both of them. These nodes depend on wireless links between them for communication. Communication between a source node and a destination node can be through direct links if they are neighbors, or through intermediate nodes' relay. Wireless multi-hop networks include MANET, wireless mesh network, and wireless sensor network.
The characteristics of a wireless multi-hop network are: 1) communication is through multi-hop forwarding over wireless links; 2) network nodes can arbitrarily move, which causes the network topology to change unpredictably; 3) self-configured and self-healing; 4) quick deployment; 5) bandwidth constrained; 6) energy constrained since most network nodes reply on battery.
Routing method is very important to wireless multi-hop networks. Node mobility causes the network topology and routes to keep changing. That frequently disrupts ongoing traffic flows and triggers more routing overhead. The network scalability is significantly impacted by increasingly triggered routing overhead as the network size extends. Therefore, the design philosophy of the routing method for wireless multi-hop networks is how to efficiently keep track of the varying network topology to maintain continuous connections and improve the network scalability, and effectively balances workloads and energy consumptions amongst network nodes to maximize the network lifetime.
The existing routing methods fall into two categories in terms of traffic forwarding: 1) source routing (e.g. DSR); 2) next-hop routing (e.g. AODV). In source routing, source nodes place a complete route path in each traffic packet, while each path node depends on the route path for forwarding the packet; in next-hop routing, each path node depends on its routing table to find the next hop for the destination in order to forward the packet. Due to the complete route path in each traffic packet, the routing overhead of source routing is greater than that of next-hop routing.
In terms of the route discovery strategy, the existing routing methods can be divided into three categories: 1) proactive routing (e.g. DSDV); 2) reactive routing (e.g. DSR, AODV); 3) hybrid routing (e.g. ZRP). In proactive routing, each node periodically exchanges routing information so that the latency of starting communication is short. However, the periodical routing information exchange causes great routing overhead. That is not meaningful if there is no need for traffic routing. More importantly, the periodical routing exchange cannot adapt to the varying network topology. In reactive routing, a source node initiates a route discovery by flooding a route request message throughout the network when the node wants to communicate with a destination node. Upon the destination node receives the route request message, the destination node unicast a route response message back to the source node. The source node depends on the route path to send traffic. When the source node finds the route path breaks, the source node re-initiates a flooding based route discovery as before. However, the flooding based route discovery greatly costs network resources and impacts other ongoing communication. In hybrid routing, the proactive routing strategy is used locally, while the reactive routing strategy is used in the whole network usually.